package violencerecursion;

/**
 * @author tongchen
 * @create 2023-03-21 16:09
 */
public class GameWin {
    public static void main(String[] args) {
        GameWin gameWin = new GameWin();
        int[]arr={1,100,1};
        System.out.println(gameWin.win(arr));
    }
    public int win(int[]arr){
        //临和博弈问题，解题思路：先手的人拿最优的选择，后手的人只能被迫接收最差的结果
        int left=0;
        int right= arr.length-1;
       return Math.max(f(arr, 0, arr.length-1),s(arr, 0, arr.length-1));
    }

    private int f(int[] arr, int left, int right) {
        //递归出口
        if(left==right){
            return arr[left];
        }
        return Math.max(arr[left]+s(arr,left+1,right),arr[right]+s(arr,left,right-1));

    }

    private int s(int[] arr, int left, int right) {
        if(right==left){
            return 0;
        }
        return Math.min(f(arr, left+1, right),f(arr, left, right-1));
    }
}
